package fun.ticsmyc.math;

import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.math
 * @date 2020-12-05 11:44
 */
public class 求组合数 {

    int mod = (int) (1e9+7);

    @Test
    public void test2(){
        System.out.println(c(4,2));
    }

    //递归方法 ，容易溢出
    public long c(int a, int b){
        if( b==0 || a==b) return 1;
        if(b ==1) return a;
        return (c(a-1,b)+c(a-1,b-1))%mod;
    }

    //递归转dp
    public long c2(int a, int b){
        int[][] dp = new int[a+1][a+1];
        for(int i=1;i<=a;++i){
            dp[i][0]=1;
            dp[i][i]=1;
            for(int j=1;j<=i/2;++j){
                dp[i][j] = (dp[i-1][j]+dp[i-1][j-1])%mod;
                dp[i][i-j]=dp[i][j];
            }
        }
        return dp[a][b];
    }


    @Test
    public void test(){
        init(2000);
        int res =0;
        for(int i=0;i<=9;++i){
            res += C(9,i);
        }
        System.out.println(res);
    }

    //乘法逆元 + 快速幂
    long [] fac; //阶乘数组
    public void init(int n ){
        fac=new long[n+1];
        fac[1] = 1;
        for(int i = 2; i <= n; i++){
            fac[i] = fac[i - 1] * 1L * i % mod;
        }
    }
    public long C(int n, int m)
    {
        if(m > n || m < 0) return 0L;
        if(m == 0 || m == n) return 1L;
        // C(n,m) = n! / (n-m)! / m!
        // a/b = a*（b的逆元）
        long res = (fac[n] * inv(fac[m] * fac[n - m])) % mod;
        return res;
    }
    public long quickPow(long base,long power){
        long result = 1;
        while(power>0){
            if( (power&1) ==1 ){
                result = (result*base)%mod;
            }
            power = power/2;
            base = (base*base )%mod;
        }
        return result;
    }

    public long inv(long x){
        return quickPow(x,mod-2)%mod;
    }
}
